class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = [0 for _ in range(n + 1)]
        count[0] = 1
        count[1] = 1
        for i in range(2, n + 1):
            x = 0
            for j in range(0, i):
                x += count[j] * count[i - 1 - j]
            count[i] = x
        return count[n]


data = Solution()
n = 2
print(data.numTrees(n))